"""
插入排序
    - 初始时手里（有序区【所以至少有一张】）只有一张牌
    - 每次（从无序区）摸一张牌, 插入到手里已有牌的正确位置
时间复杂度： O(n**2)
稳定性：稳定
"""
import random

from SortingAlgorithm.cal_time.cal_time import cal_time


@cal_time(name="插入排序时间")
def insert_sort(li):
    for i in range(1, len(li)):  # i 表示摸到的牌的下标  有序区【所以至少有一张】
        tmp = li[i]
        j = i - 1  # j指的是手里(摸到的牌的左边挨着的)的牌的下标
        while j >= 0 and li[j] > tmp:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp


if __name__ == "__main__":
    # li = [1,2,4,7,9,5,6,6,10,8]
    li = list(range(100000))
    import time
    random.shuffle(li)
    # print(li)
    start = time.time()
    # sorted(li)
    li.sort()
    delta = time.time() - start
    print(delta)
    # print(li)
    # insert_sort(li)
    # print(li)
